/**
 * 96. 不同的二叉搜索树
 * https://leetcode-cn.com/problems/unique-binary-search-trees/
 */
public class Solutions_96 {
    public static void main(String[] args) {
//        int n = 2;  // output: 2
        int n = 3;  // output: 5

        int result = numTrees(n);
        System.out.println(result);
    }

    /**
     * 卡塔兰数 C(n)
     * 令 C(n) = 1，则 C(n + 1) = ((2 * (2n + 1)) * C(n)) / (n + 2)
     */
    public static int numTrees(int n) {
        long C = 1;
        for (int i = 0; i < n; i++) {
            C = (2 * (2 * i + 1) * C) / (i + 2);
        }
        return (int) C;
    }

    /**
     * 动态规划
     */
    public static int numTrees4(int n) {
        // dp[3] = 5，表示 [1,2,3] 3 个节点时，共有 5 种不同结构的二叉搜索树
        int[] dp = new int[n + 1];
        // 没有节点和一个节点，都可以组成一个不同结构
        dp[0] = dp[1] = 1;
        // 第 i 个节点时，计算不同结构的数量
        for (int i = 2; i <= n; i++) {
            // j 作为根节点，能够组成的不同结构二叉搜索树 = 左子树不同结构数 * 右子树不同结构树
            // [1, i] 都可以作为根节点
            for (int j = 1; j <= i; j++) {
                // 左子树节点数量：j - 1，即 [1, j - 1]，或者 [1, j)
                // 右子树节点数量：i - j，即 [i + 1, n]，或者 (i, n]
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }

    /**
     * 记忆化递归（）
     */
    private static int[] map = null;
    public static int numTrees3(int n) {
        map = new int[n + 1];
        map[0] = map[1] = 1;
        return calc(n);
    }

    /**
     * 使用记忆化来减少大量的重复递归计算
     * 因为每个子问题的递归中 for 循环都是从 1 开始的
     * 例如：n = 3 时
     * i = 1 时，通过 rightRes = calc(n - i) = calc(2)，已经计算得到 2 个节点时，能够组成的不同结构数量
     * 而 i = 3 时，leftRes = calc(i - 1) = calc(2)，又要递归计算 2 个节点时，能够组成的不同结构数量
     * 而通过节点数量，能够组成的不同结构二叉搜索树数量又是固定的，所以可以将每次记录的结果记录下，
     * 供后面的计算使用
     */
    public static int calc(int n) {
        if (map[n] > 0) {
            // 如果已经计算并记录过 n 个节点时不同结构的数量，直接返回结果，无需循环递归子问题
            return map[n];
        }
        int res = 0;
        for (int i = 1; i <= n; i++) {
            int leftRes = calc(i - 1);
            int rightRes = calc(n - i);
            res += leftRes * rightRes;
        }
        map[n] = res;
        return res;
    }

    /**
     * 递归（2826ms）
     */
    public static int numTrees2(int n) {
        if (n <= 1) {
            // 递归结构条件：n 为 0 表示空子树（也是一种结构），为 1 表示一个节点
            return 1;
        }
        int res = 0;
        // 不同结构的二叉搜索树数量计算方式：将 [1, n] 中的每个数值，作为树的根节点，两侧的数值分别作为左右子树
        // 递归计算，重复子问题
        for (int i = 1; i <= n; i++) {
            // 数组区间 [1, i - 1] 部分作为左子树，[i + 1, n] 部分，作为右子树
            // 递归计算给定值的情况下，左，在子树分别有多少种不同的结构
            // i 作为根节点时，能够组成的不同结构数量 = 左子树结构数量 * 右子树结构数量
            int leftRes = numTrees2(i - 1);
            int rightRes = numTrees2(n - i);
            res += leftRes * rightRes;
        }
        return res;
    }
}
